// 分治 快排 数组划分、数组分块
// 使用 3 指针将数组分为 4 块：[0, left], [left + 1, cur], [cur, right - 1], [right, n - 1]
// [0, left] - left 维护的区间
// [left + 1, cur] - cur 维护的区间
// [cur, right - 1] - 待处理的区间
// [right, n - 1] - right 维护的区间
// cur 负责扫描数组
// 快排的核心就是使用 三指针 方法，只是多了找基准元素的一步
// 找基准元素最优秀的方式就是区间内选择区间内的随机元素，时间复杂度可以逼近 O(n * log n)

// 例题 4：
// 仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。
// 请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
//
//        示例 1：
//
//        输入：stock = [2,5,7,4], cnt = 1
//        输出：[2]
//        示例 2：
//
//        输入：stock = [0,2,3,6], cnt = 2
//        输出：[0,2] 或 [2,0]
//
//
//        提示：
//
//        0 <= cnt <= stock.length <= 10000
//
//        0 <= stock[i] <= 10000

// 解题思路：
// 本题使用快速选择算法 - 快速选择算法是基于快排的
// 使用 三指针 数组划分作为快排的核心思想 数组分块：[0, left], [left + 1, right - 1], [right, n - 1]
// 快速选择 - 即找第 k 大元素是落在哪个区间
// 落在 [right, n - 1]，递归继续找 cnt - (right - start) 个元素
// 落在 [left + 1, right - 1]，直接返回
// 落在 [0, left]，递归找 前 cnt 个元素

import java.util.Random;

public class InventoryManagement {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int[] ret = new int[cnt];
        int n = stock.length;
        qsort(stock, 0, n - 1, cnt);
        for(int i = 0; i < cnt; i++) ret[i] = stock[i];
        return ret;
    }
    public void qsort(int[] stock, int start, int end, int cnt){
        if(start >= end) return;
        int left = start - 1; int right = end + 1;
        int cur = start;
        Random r = new Random();
        int index = r.nextInt(end - start + 1) + start;
        int key = stock[index];
        while(cur < right){
            if(stock[cur] < key) swap(stock, ++left, cur++);
            else if(stock[cur] == key) cur++;
            else swap(stock, --right, cur);
        }
        if(cnt <= left - start + 1) qsort(stock, start, left, cnt);
        else if(cnt <= right - start) return;
        else qsort(stock, right, end, cnt - (right - start));
    }
    public void swap(int[] nums, int i , int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
